#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : bheap.py
@Time    : 2022/12/01 23:08:13
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 利用列表实现完全二叉树，描述二叉最小堆
"""

# 完全二叉树中，除了最底层，其他每一层的节点都是满的。
# 完全二叉树的另一个有趣之处在于，可以用一个列表来表示它，
# 而不需要采用“列表之列表”或“节点与引用”表示法。
# 对于在列表中处于位置p的节点来说，它的左子节点正好处于位置2p；
# 同理，右子节点处于位置2p+1
# 给定列表中位置n处的节点，其父节点的位置就是n/2。
# 堆的有序性是指：对于堆中任意元素x及其父元素p，p都不大于x。
class BinaryHeap:
    def __init__(self):
        self.hlist = [0]  # 为了实现上述的索引方式，需要下标从1个索引
        self.size: int = 0

    def perc_up(self, i):  # 上浮
        while (i >> 1) > 0:
            t = i >> 1
            if self.hlist[i] < self.hlist[(t)]:
                self.hlist[i], self.hlist[(t)] = self.hlist[(t)], self.hlist[i]
            i = t

    def insert(self, k):
        self.hlist.append(k)
        self.size += 1
        self.perc_up(self.size)

    def perc_down(self, i):
        while (i << 1) <= self.size:
            t = self.min_child(i)
            if self.hlist[t] < self.hlist[i]:
                self.hlist[t], self.hlist[i] = self.hlist[i], self.hlist[t]
            i = t

    def min_child(self, i) -> int:
        t = i << 1
        if t >= self.size:
            return t

        if self.hlist[t] < self.hlist[t + 1]:
            return t

        return t + 1

    def del_min(self):
        ret = self.hlist[1]
        self.hlist[1] = self.hlist[self.size]
        self.hlist.pop()
        self.size -= 1
        self.perc_down(1)
        return ret

    def build_heap(self, lis):
        # 叶子节点不用下沉
        i = len(lis) // 2  # 最后一个叶子节点的父节点
        self.size = len(lis)
        self.hlist = [0] + lis
        while i > 0:
            self.perc_down(i)
            i = i - 1
